Inteligencia Artificial

1 Contenido de la clase

Sintaxis de la lógica de primer orden [00:00-01:45]

Una fórmula de LPO se construye con:

• Términos: constantes que nombran objetos (p. ej. Ali, Otto), variables (x, y, z) y funciones aplicadas a términos (p. ej. la suma de dos números) [01:01-01:20].
• Fórmulas atómicas: un predicado aplicado a términos (p. ej. "x es un entero par") [01:24-01:28].
• Conectivos aplicados a fórmulas: ¬, ∧, ∨, →, ↔ [01:31-01:38].
• Cuantificadores aplicados a fórmulas: ∀ y ∃ [01:39-01:44].

∀x (Par(x) ∧ Mayor(x, 2) → SumaDeDosPrimos(x)) [00:45-00:51]

Se retoma la frase de la clase anterior: "para todo x, si x es un entero par mayor que 2, entonces x es la suma de dos primos" [00:45-00:51].

Cuantificadores y su negación [02:19-03:11]

• ∀x P(x): para todo x se cumple P(x).
• ∃x P(x): existe algún x tal que P(x).

La negación de un cuantificador lo transforma en el otro:

¬∀x P(x) ≡ ∃x ¬P(x)  ·  ¬∃x P(x) ≡ ∀x ¬P(x) [02:55-03:00]

El orden de los cuantificadores importa [04:11-05:21]

Se comparan dos frases que parecen iguales pero no lo son:

• "Para todo estudiante existe un curso que le gusta" (∀e ∃c): cada estudiante puede tener su propio curso.
• "Existe un curso que a todos los estudiantes les gusta" (∃c ∀e): un mismo curso debe gustarle a todos [04:19-04:47].

El profesor lo explica con dos ciclos anidados: en ∀x∃y se recorre x y por cada x se busca un y (el ciclo termina en cuanto lo encuentra); en ∃y∀x hay que encontrar un y que funcione para todo x [04:51-05:21].

Ejemplos de traducción a LPO [05:24-06:05]

• "Todos los estudiantes saben inteligencia artificial" = ∀x (Estudiante(x) → SabeIA(x)) [05:28-05:35].
• "Existe un curso que todo estudiante ha tomado" = ∃c (Curso(c) ∧ ∀e (Estudiante(e) → HaTomado(e, c))) [05:41-05:49].
• Si el curso Q es un concepto, entonces el estudiante que lo tomó sabe ese concepto [05:51-06:00].

Del lenguaje natural a la lógica: el reto es la traducción [06:07-07:18]

Hoy mucha gente parte del lenguaje natural, lo traduce a lógica de primer orden (u otras lógicas) y desde ahí hace inferencia, porque existen muy buenos mecanismos para hacerlo [06:19-06:41]. El ejercicio principal es la traducción [06:32]. Al traducir se especifica qué es cada cosa (qué es un estudiante, qué es un curso) y luego esas expresiones se evaluarán como verdaderas o falsas [06:55-07:11].

Modelos en lógica de primer orden [07:43-09:03] [09:33-21:23]

Un modelo representa una situación del mundo. En lógica proposicional un modelo era una asignación de valores de verdad (1/0) a las variables (p. ej. "lluvia", "mojado") [07:51-08:08]. En lógica de primer orden un modelo es más rico:

• Un dominio (universo) de objetos, no vacío (todo modelo debe tener al menos un objeto), p. ej. {o1, o2, o3} [09:33-09:51].
• Cada constante se interpreta como un objeto del dominio: John→o1, Bob→o2 [20:03-20:12].
• Cada predicado se interpreta como una relación sobre los objetos (p. ej. "es estudiante") [09:55-20:00].
• Las funciones mapean objetos a objetos (p. ej. agrupar o1 y o3) [09:57-20:00].

Se recorren varios "mundos" (mundo 1, 2 y 3) que interpretan las mismas constantes y predicados de maneras distintas, p. ej. quién es estudiante [20:55-21:09].

Suposiciones sobre los modelos [22:35-23:28]

• Suposición de nombres únicos: cada objeto tiene a lo más una constante (no llamar "John" y "Bob" al mismo objeto) [22:47-22:58].
• Cerradura de dominio: cada objeto del dominio tiene al menos una constante [23:01-23:14].
• Juntas garantizan una relación uno a uno entre constantes y objetos [23:16-23:18]. El profesor advierte que no hay que equivocarse con las suposiciones en el examen [23:23-23:28].

Suposición de mundo cerrado [23:29-24:13]

En algunas interpretaciones se supone que todo lo que no está dicho es falso [23:33-23:37]. Ejemplo con argumentos de adolescentes: "no me dijiste que estaba prohibido hacer eso" → se asume que lo no dicho es prohibido [23:39-23:45]. También existe la interpretación contraria (lo que no está definido…), que puede llevar a conclusiones completamente diferentes [23:45-23:51].

Elaboración de la base de conocimiento [24:43-25:41]

Se encadenan predicados: si "x es estudiante de la U" implica "x es persona", y "x es profesor de la U" implica "x es persona", ambas implican "persona de la U" [24:43-25:05]. Cuantos más objetos y combinaciones haya, más grande es el mundo que hay que revisar [25:26-25:35].

Sustitución [29:20-30:00]

Una sustitución es un mapeo que reemplaza variables por términos (p. ej. {X→a, Y→…}). Al aplicar una sustitución a una expresión se obtiene una nueva expresión [29:22-29:31].

Unificación y unificador más general [40:30-41:27] [44:53-45:46]

La unificación busca una sustitución tal que la sustitución de T1 sea igual a la sustitución de T2; si no existe tal sustitución, las expresiones no se unifican [40:30-40:37]. Se busca el unificador más general (MGU) [40:55-40:57]. Se usa para "comunicar" (unificar) expresiones, p. ej. A1' con A1, y en el ejemplo "X toma el curso Y, Y es de concepto Z, entonces X sabe Z" [44:53-45:46].

Resolución en lógica de primer orden [63:25-68:06]

Para aplicar la resolución se convierte la base de conocimiento a forma normal conjuntiva (CNF):

• Eliminar implicaciones (→ se reescribe con ∨ y ¬) [65:33-65:41].
• Empujar las negaciones hacia adentro (leyes de De Morgan y negación de cuantificadores: ¬∀ se vuelve ∃, ¬∃ se vuelve ∀) [65:43-66:00].
• Renombrar variables para que no haya confusiones entre alcances [66:00-66:12].
• Eliminar los cuantificadores existenciales sustituyéndolos por funciones de Skolem [66:18-66:33].
• Distribuir ∨ sobre ∧ (paso equivalente al de lógica proposicional) [66:37-66:46].
• Eliminar los cuantificadores universales [66:58-67:03].

Con las cláusulas en CNF se aplica la regla de resolución con unificación: se cancelan literales complementarios, p. ej. Ama(z, x) con ¬Ama(u, v) [67:49-67:53]. Ejemplo con "animal", "ama", "no ama" y "alimenta" [67:23-68:00].

Ejercicio: ¿Sócrates es mortal? [68:08-68:48]

• Todo humano es mortal: ∀x (Humano(x) → Mortal(x)).
• Sócrates es humano.
• Pregunta: ¿Sócrates es mortal? [68:10-68:17].

Se aplica resolución: se niega la conclusión, se unifica la variable x con Sócrates y se llega a la contradicción (mortal y no mortal), lo que prueba que Sócrates es mortal [69:15-69:30].

Ejemplo clásico: "Cualquiera que ama todos los animales" [69:41-69:59]

• Cualquiera que ama todos los animales es amado por alguien [69:44].
• Cualquiera que mata un animal no es amado por nadie [69:48].
• Jack ama todos los animales [69:51].
• Jack o Curiosity mató a la gata [69:53].
• Pregunta: ¿Curiosity mató a la gata? (ejemplo clásico de Russell y Norvig) [69:55-69:59].

Complementos y precisiones

• Estandarizar las variables aparte (standardizing apart): antes de unificar hay que renombrar las variables de cada cláusula para evitar colisiones (p. ej. Loves(x, F(x)) y Loves(Jack, x) solo unifican tras renombrar una de las x). Es imprescindible para la resolución.
• Dominio no vacío: en LPO todo modelo debe tener al menos un objeto.
• Igualdad (=): predicado especial de LPO; se maneja con axiomas de igualdad (reflexividad, simetría, transitividad, sustitución) o con paramodulación.
• Encadenamiento hacia adelante/atrás en LPO: las cláusulas definidas de primer orden se usan con forward/backward chaining con unificación; el backward chaining es la base de Prolog.
• Resolución con unificación (lifting lemma): todo paso proposicional se "eleva" a LPO sustituyendo variables; por eso la resolución en LPO es refutation-complete.

2 Puntos destacados / Lo que hay que saber

3 Actividades y tareas pendientes

No se indicaron tareas con fecha de entrega en esta clase. El profesor dejó prácticas recomendadas:

4 Dudas que podrían examinar

5 Sitios o recursos para visitar

6 Glosario de términos

• Término: constante, variable o función aplicada a términos.
• Fórmula atómica: un predicado aplicado a términos.
• Cuantificador universal (∀): "para todo x…".
• Cuantificador existencial (∃): "existe algún x…".
• Modelo: una situación del mundo; en LPO, un dominio de objetos con constantes, predicados y funciones interpretados.
• Dominio (universo): el conjunto de objetos sobre el que se interpreta la lógica.
• Suposición de nombres únicos: cada objeto tiene a lo más una constante.
• Cerradura de dominio: cada objeto tiene al menos una constante.
• Mundo cerrado: todo lo que no está dicho se asume falso.
• Sustitución: mapeo que reemplaza variables por términos.
• Unificación: hallar una sustitución que haga idénticas dos expresiones.
• Unificador más general (MGU): la sustitución más general que unifica dos expresiones.
• CNF (forma normal conjuntiva): conjunción de cláusulas (disyunciones de literales).
• Función de Skolem: función introducida para eliminar un cuantificador existencial.
• Resolución: regla de inferencia que cancela literales complementarios tras unificar.
• Estandarizar variables aparte: renombrar las variables de cada cláusula para evitar colisiones antes de unificar.
• Igualdad (=): predicado especial de LPO; requiere axiomas de igualdad o paramodulación.
• Lifting lemma: garantiza que la resolución proposicional se puede elevar a LPO con unificación (resolución refutation-complete).

7 Mapa mental textual

• Inteligencia Artificial · Clase 11 · Lógica de primer orden
  • Sintaxis
    • Términos: constantes, variables, funciones
    • Fórmulas atómicas: predicados aplicados a términos
    • Conectivos y cuantificadores (∀, ∃)
  • Semántica: modelos
    • Dominio de objetos (universo)
    • Constantes → objetos; predicados → relaciones; funciones → funciones
    • Suposiciones: nombres únicos, cerradura de dominio, mundo cerrado
  • Traducción del lenguaje natural a LPO
    • El orden de los cuantificadores importa (∀e∃c vs ∃c∀e)
  • Inferencia
    • Sustitución
    • Unificación y unificador más general
    • Resolución: CNF + funciones de Skolem + cancelar literales
  • Ejercicios clásicos
    • Sócrates es mortal
    • "Curiosity mató a la gata" (Russell y Norvig)